import { Compare, defaultCompare, ICompareFunction, swap } from '../../util';
/**
 * 快速排序：将数组分隔成两段，分隔时会对数组进行简单排序，将较小项移到分隔点
 * 左边，对应右边是较大项。但由于左右两边里面也没顺序，那将左右两边也进行分隔
 * 处理，直到不能再分隔，这样使得每个小段都有了顺序，进而整段也是有了顺序。
 * @param array 目标数组
 * @param left 左边界限
 * @param right 右边界限
 * @param compareFn 比较函数
 * 这样看来快速排序也是分而治之的一种应用，跟归并排序很像，两者区别就是：一个是
 * 分开时简单分类（大致顺序）后面直接合并， 另一个是分开时不处理后面合并时再排序。
 *
 * 快速排序的空间复杂度都是O(1)，没有每轮借助临时数组；快速排序的最好、平均时间复
 * 杂度都是O(nlogn)；最差时间复杂度是O(n^2)，因为当数组原本是降序的，要求排成升序
 * 的，并且基准点取的是最左边时，算出的下一轮的基准点还是最左边（一般返回给下一轮的
 * 应该是中间点），这就导致它没有了左右两边数组的递归了，而是就是它本身去排序了，
 * 退化成n^2这样的排序了。
 */
export const quickSort = (
    array: any[],
    compareFn: ICompareFunction<any> = defaultCompare,
    left: number = 0,
    right: number = array.length - 1,
) => {
    if (left < right) {
        // 将数组分隔成左右两端，分隔的同时将小的移到左边那段，大的移到右边那段，m就是最后的分隔点
        const m = partition(array, left, right, compareFn);
        // 对m左边进行同样的分隔处理
        quickSort(array, compareFn, left, m - 1);
        // 对m右边进行同样的分隔处理
        quickSort(array, compareFn, m + 1, right);
    }
    // 直到left === right或left > right，也就是没有可分隔的了，那意味着每一小段都有顺序，整段也有了顺序
    return array;
};

/**
 * 以左边第一个为基准点，遍历该数组，将小的移到左边那么大的被挤到右边
 * @param array 目标数组
 * @param left 左边界限
 * @param right 右边界限
 * @param compareFn 比较函数
 */
const partition = (array: any[], left: number, right: number, compareFn: ICompareFunction<any>) => {
    const pivot = array[left]; // 最左边作为基准项，记住基准项的值
    let m = left; // 较小项的放置点

    // 从基准项后面开始遍历
    for (let i = left + 1; i <= right; i ++) {
        // 如果当前项比基准项小，就将当前项和基准项的左边元素对换，为了让较小项紧挨基准项的左边 {1}
        if (compareFn(array[i], pivot) === Compare.LESS_THAN) {
            swap(array, i, ++ m);
        } // 没进if的项就是比基准项大了，它们处于最右边较小项的右边 {2}
    }
    // 让最右边较小项和基准项交换，就达到了较小项在基准项的左边、较大项在基准项的右边的目的（分隔{1}和{2}）
    swap(array, left, m);
    // 返回分隔点
    return m;
};
